class node {
    constructor(key = '',value = '') {
        this.key = key
        this.value = value
        this.next = null
        this.prev = null
    }
}

class LinkList {
    constructor() {
        this.head = new node('head','head')
        this.tail = new node('tail','tail')
        this.head.next = this.tail
        this.tail.prev = this.head
    }
    append(node) {
        node.next = this.head.next
        node.prev = this.head
        this.head.next.prev = node
        this.head.next = node
    }
    pop() {
        let node = this.tail.prev;
        node.prev.next = this.tail
        this.tail.prev = node.prev
        return node
    }
    delete(node) {
        node.prev.next = node.next
        node.next.prev = node.prev
    }
}
class LRU {
    constructor(cap) {
        this.list = new LinkList()
        this.map = new Map()
        this.capacity = cap
    }
    put(key,value) {
        if (this.map.has(key)) {
            const cur = this.map.get(key)
            cur.value = value
            this.list.delete(cur)
            this.list.append(cur)
        }
        else {
            let cur = new node(key,value)
            if (this.map.size >= this.capacity) {
                const node1 = this.list.pop()
                this.map.delete(node1)
            }
            this.map.set(key,cur)
            this.list.append(cur)
        }
    }
    get(key) {
        if (!this.map.has(key)) {
            return -1
        }
        else {
            const node = this.map.get(key)
            this.list.delete(node)
            this.list.append(node)
            return node.value
        }
    }
}

const obj = new LRU(2);
obj.put(1, 1);// 1
obj.put(2, 2);// 2 -> 1
console.log(obj.get(1)); // 1 -> 2
obj.put(3, 3);// 3 -> 1
console.log(obj.get(2));// 此时缓存里没有2的位置了，因此会返回-1
obj.put(4, 4);// 4 -> 3
console.log(obj.get(1));// 此时缓存里没有1的位置了，因此会返回-1
console.log(obj.get(3));// 3 -> 4
console.log(obj.get(4));// 4 -> 3

